// https://www.lintcode.com/problem/1219

// 先对于加热器数组排序。 对于每个房屋i，在加热器数组里使用
// 二分查找找到距离房屋i最近的加热器的位置，最后的答案为所有房屋答案的最大值。
class Solution {
public:
    /**
     * @param houses: positions of houses
     * @param heaters: positions of heaters
     * @return: the minimum radius standard of heaters
     */
    int findRadius(vector<int> &houses, vector<int> &heaters) {
        sort(heaters.begin(), heaters.end());
        int ans = 0;
        for (int i = 0; i < houses.size(); ++i) {
            ans = max(ans, closeHeater(houses[i], heaters));
        }
        return ans;
    }
    int closeHeater(int house, vector<int> &heaters) {
        int start = 0;
        int end = heaters.size() - 1;
        while (start + 1 < end) {
            int mid = (end - start) / 2 + start;
            if (heaters[mid] == house) {
                return 0;
            } else if (heaters[mid] < house) {
                start = mid;
            } else {
                end = mid;
            }
        }
        return min(abs(house - heaters[start]), abs(house - heaters[end]));
    }
};